perm filename PAGE30[00,BGB] blob
sn#046259 filedate 1973-06-06 generic text, type T, neo UTF8
~F84. SMOOTHING.
In CRE the term "smoothing" refers more to the problem of
breaking a manifold (polygon) into functions (arcs), rather than to
the problem of fitting functions to measured data. The smoothing
step, converts the polygons of vertical and horizontal vectors into
polygons of arcs. For the present the term "arc" means "linear arc"
which is a line segment. Fancier arcs: circular and cubic spline
were implemented and thrown out mostly because they were of no use
to higher processes such as the polygon compare which would break
the fancier arcs back down into linear vectors for computing areas,
inertia tensors or mere display buffers.
Smoothing is applied to each polygon of a level. To start
the smoothing, a ring of two arcs is formed (a bi-gon) with one arc
at the uppermost left and the other at the lowermost right of the
given vector polygon. Next a recursive make arc operation, MKARC, is
is appled to the two initial arcs. Since the arc given to MKARC is
in a one to one correspondece with a doubly linked list of vectors;
MKARC checks to see whether each point on the list of vectors is
close enough to the approximating arc. MKARC returns the given arc
as good enough when all the sub vectors fall within a given width;
otherwise MKARC splits the arc in two and places a new arc vertex on
the vector vertex that was furthest away from the original arc.
The two large images in figure-7, illustrate a polygon
smoothed with arc width tolerances set at two different widths in
order to show one recursion of MKARC. The eight smaller images
illustrate the results of setting the arc width tolerance over a
range of values. Because of the dekinking mentioned earlier the arc
width tolerance can be equal to or less than 1.0 pixels and still
expect a substantial reduction in the number of vectors it takes to
describe a contour polygon.
A final important smoothing detail is that the arc width
tolerance is actually taken as a function of the highest contrast
vector found along the arc; so that high contrast arcs are smoothed
with much smaller arc width tolerances than are low contrast arcs.
After smoothing, the contrast across each arc is computed and the
ring of arcs replaces the ring of vectors of the given polygon.
(Polygons that would be expressed as only two arcs are deleted).
~I1973,800;F8- 30 -